package day6;
import day5.TreeNode;

import java.util.*;

public class ch3 {


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(preorder[i],i);
        }
        TreeNode root = new TreeNode(preorder[0]);
        fun(map,preorder,inorder,root,0,0,inorder.length-1);
        return root;


    }

    public void fun(HashMap<Integer,Integer> map,int[] preorder, int[] inorder,TreeNode node,int p,int l,int r){
        int mid = map.get(node.val);

        int left = mid-l;
        int right = r-mid;

        if(left>0){
            TreeNode nodel = new TreeNode(preorder[p+1]);
            node.left = nodel;
            fun(map,preorder,inorder,nodel,p+1,l,mid-1);
        }
        if(right>0){
            TreeNode noder = new TreeNode(preorder[p+left+1]);
            node.right = noder;
            fun(map,preorder,inorder,noder,p+left+1,mid+1,r);
        }
    }


    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null) return list;

        TreeNode node = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(node);

        while (!stack.isEmpty()){
            node = stack.pop();
            list.add(node.val);
            if(node.right!=null) stack.push(node.right);
            if(node.left!=null) stack.push(node.left);
        }

        return list;

    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();

        TreeNode node = root;

        while (node!=null||!stack.isEmpty()){
            while (node!=null){
                stack.push(node);
                node = node.left;
            }
            TreeNode tep = stack.pop();
            list.add(tep.val);
            node = tep.right;
        }

        return list;

    }


    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();

        TreeNode node = root;
        TreeNode last = null;

        while (node!=null||!stack.isEmpty()){
            while (node!=null){
                stack.push(node);
                node = node.left;
            }
            TreeNode tep = stack.pop();
            if(tep.right==null||tep.right==last){
                list.add(tep.val);
                last = tep;
                node = null;

            }else {
                stack.push(tep);
                node = tep.right;
            }


        }

        return list;


    }







}
